package SortAlgorithm;

import com.alibaba.fastjson.JSON;

import java.util.Arrays;

public class 插入排序 implements ISort{

    /**
     * 将一元素对 一个已经排序好的序列 进行插入,插入后维护原排序规则
     */

    @Override
    public int[] sort(int[] arr) {
        return insertionSort(arr);
    }

    public int[] insertionSort(int[] arr){

        for (int i = 1; i < arr.length; i++) {

            //如果进不到这个if里面,那么就是最优情况 O(n)
            if(arr[i]<arr[i-1]) {//优化点:小于序列的末尾,才进行排序
                for (int j = 0; j < i; j++) {
                    if (arr[i] < arr[j]) {
                        swap(arr, i, j);
                    }
                }
            }

        }

        return arr;
    }

    private void swap(int[] arr,int index1,int index2){
        int temp=arr[index1];
        arr[index1]=arr[index2];
        arr[index2]=temp;
    }

    public static void main(String[] args) {
        插入排序 n=new 插入排序();
        int[] arr={4,2,3,4,5,6,1,2,4,3,5,1,5,2,5,6,1,2,5};
        int[] result = n.insertionSort(arr);
        System.out.println(JSON.toJSONString(result));
        Arrays.sort(arr);
        System.out.println(JSON.toJSONString(arr));
    }

}
